//
//  sorting.swift
//  sorting
//
//  Created by lhc on 2023/8/17.
//

import Foundation

class SelectSort {
    
    static func sort<E: Comparable>(l: [E]) -> [E] {
        var mutableL = l
        for i in 0..<mutableL.count {
            
            var miniIndex = i
            for j in i..<mutableL.count {
                if mutableL[j] < mutableL[miniIndex] {
                    miniIndex = j
                }
            }
            
            let temp = mutableL[i]
            mutableL[i] = mutableL[miniIndex]
            mutableL[miniIndex] = temp
        }
        return mutableL
    }
    
    static private func exchange<E: Comparable>(arr: inout [E], i: Int, j: Int) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}

class InsertSort {
    static func sort<E: Comparable>(l: [E]) -> [E] {
        var mutableL = l
        
        for i in 1..<mutableL.count {
            let a = mutableL[i]
            var j = i
            
            while j > 0 && a < mutableL[j - 1] {
                mutableL[j] = mutableL[j - 1]
                j -= 1
            }
            mutableL[j] = a
        }
        
        return mutableL
    }
}

class MergeSort {
    
    static func sort<E: Comparable>(l: inout [E]) {
        sortByRecursion(l: &l, left: 0, right: l.count - 1)
    }
    
    static private func sortByRecursion<E: Comparable>(l: inout [E], left: Int, right: Int) {
        if left >= right {
            return
        }
        
        let mid = left + (right - left) / 2
        sortByRecursion(l: &l, left: left, right: mid)
        sortByRecursion(l: &l, left: mid + 1, right: right)
        if l[mid] > l[mid + 1] {
            merge(list: &l, left: left, mid: mid, right: right)
        }
    }
    
    static func sortFromBelow<E: Comparable>(l: inout [E]) {
        var step = 1
        let length = l.count
        
        while step < length {
            
            var left = 0
            
            while left + step < length {
                let right = min(left + step * 2 - 1, length - 1)
                let mid = left + step - 1
                if l[mid] > l[mid + 1] {
                    merge(list: &l, left: left, mid: mid, right: right)
                }
                left += step * 2
            }
            
            
            step *= 2
        }
    }
    
    static private func merge<E: Comparable>(list: inout [E], left: Int, mid: Int, right: Int) {
        let slice = list[left...right]
        let temp = Array(slice)
        
        var i = left
        var j = mid + 1
        var n = left
        
        while n <= right {
            if i > mid {
                list[n] = temp[j - left]
                j += 1
            }else if j > right {
                list[n] = temp[i - left]
                i += 1
            }else if temp[i - left] <= temp[j - left] {
                list[n] = temp[i - left]
                i += 1
            }else if temp[i - left] > temp[j - left] {
                list[n] = temp[j - left]
                j += 1
            }
            
            n += 1
        }
        
    }
}

class QuickSort {
    
    static func sort<E: Comparable>(arr: inout [E])  {
        sortByRecursion(arr: &arr, left: 0, right: arr.count - 1)
    }
    
    static private func sortByRecursion<E: Comparable>(arr: inout [E], left: Int, right: Int) {
        if left >= right {
            return
        }
        
        let j = partition(arr: &arr, left: left, right: right)
        sortByRecursion(arr: &arr, left: left, right: j)
        sortByRecursion(arr: &arr, left: j + 1, right: right)
    }
    
    static private func partition<E: Comparable>(arr: inout [E], left: Int, right: Int) -> Int {
        randomV(arr: &arr, left: left, right: right)
        
        let v = arr[left]
        var i = left + 1
        var j = left
        while i <= right {
            if arr[i] < v {
                j += 1
                exchange(arr: &arr, i: i, j: j)
            }
            i += 1
        }
        exchange(arr: &arr, i: left, j: j)
        return j
    }
    
    static func sortThreeWays<E: Comparable>(arr: inout [E]) {
        sortByRecursionThreeWays(arr: &arr, left: 0, right: arr.count - 1)
    }
    
    static private func sortByRecursionThreeWays<E: Comparable>(arr: inout [E], left: Int, right: Int) {
        if left >= right {
            return
        }
        
        let (lessThan, greatThan) = partitionThreeWays(arr: &arr, left: left, right: right)
        sortByRecursionThreeWays(arr: &arr, left: left, right: lessThan)
        sortByRecursionThreeWays(arr: &arr, left: greatThan, right: right)
    }
    
    static private func partitionThreeWays<E: Comparable>(arr: inout [E], left: Int, right: Int) -> (Int, Int) {
        randomV(arr: &arr, left: left, right: right)
        
        let v = arr[left]
        var i = left + 1
        var lessThan = left
        var greatThan = right + 1
        while i < greatThan {
            if arr[i] < v {
                lessThan += 1
                exchange(arr: &arr, i: i, j: lessThan)
                i += 1
            }else if arr[i] == v {
                i += 1
            }else if arr[i] > v {
                greatThan -= 1
                exchange(arr: &arr, i: i, j: greatThan)
            }
        }
        exchange(arr: &arr, i: left, j: lessThan)
        
        return (lessThan, greatThan)
    }
    
    /// 随机选择中间值
    static private func randomV<E: Comparable>(arr: inout [E], left: Int, right: Int) {
        let random = Int.random(in: left...right)
        exchange(arr: &arr, i: left, j: random)
    }
    
    static private func exchange<E: Comparable>(arr: inout [E], i: Int, j: Int) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}


class BubbleSort {
    static func sort<E: Comparable>(arr: inout [E]) {
        let count = arr.count
        
        // arr[count - i, count) 是排好序的
        var i = 0
        while i < count {
            // 记录最后一次交换的index,后面因为都没交换说明后面是有序的
            var lastSwappedIndex = 0
            
            for j in 0..<count - i - 1 {
                if arr[j] > arr[j + 1] {
                    BubbleSort.exchange(arr: &arr, i: j, j: j + 1)
                    lastSwappedIndex = j + 1
                }
            }
            
            // i 赋值为总数减去有序的数字数量
            i = count - lastSwappedIndex
            // 如果last_swapped_index == 0 说明都有序 那么i就会 == count 结束循环
        }
    }
    
    static private func exchange<E: Comparable>(arr: inout [E], i: Int, j: Int) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}


class ShellSort {
    
    static func sort<E: Comparable>(arr: inout [E]) {
        
        // 希尔排序交换的间隔为h 每次都/2 交换的距离越来越小
        var h = arr.count / 2
        
        while h >= 1 {
            
            // 内部是插入排序，不过每次比较的是和间隔前h个的元素
            // 因为往前比较，所以第一个元素是h
            for i in h..<arr.count {
                    
                let t = arr[i]
                var j = i
                while j - h >= 0 && t < arr[j - h] {
                    // 当j - h 还没越界，同时t这个数小于间隔前h的那个元素
                    // 把arr[j - h]的元素向后挪h位
                    arr[j] = arr[j - h]
                    j -= h
                }
                arr[j] = t
            }
            
            h /= 2
        }
    }
}
